package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

/**
 * @author Fengkai  等和子集
 * @creat 2023/3/29
 */

import org.junit.Test;

import java.util.*;


public class EquimolecularSet {
    //暴力递归
    public static boolean check(List<Integer> list, int number, int beforeNumber) {
        if (list == null)
            return true;
        if (number == beforeNumber && list.size() == 0) {
            return true;
        }
        boolean statu = false;
        for (int i = 0; i < list.size(); ++i) {
            List<Integer> mySubList = new ArrayList<>();
            for (int j = 0; j < list.size(); ++j) {
                if (i != j) {
                    mySubList.add(list.get(j));
                }
            }
            if (list.get(i) == number) {
                statu = statu || check(mySubList, beforeNumber, beforeNumber);
            } else if (list.get(i) < number) {
                statu = statu || check(mySubList, number - list.get(i), beforeNumber);
            }
        }
        return statu;
    }

    public static void main(String[] args) {
        try {
            Scanner scan = new Scanner(System.in);
            int t = scan.nextInt();
            if (t < 1 || t > 50) {
                System.out.println("input error");
                return;
            }
            int[] scoreArray = new int[t];
            for (int i = 0; i < scoreArray.length; ++i) {
                scoreArray[i] = scan.nextInt();
            }
            int sum = 0;
            List<Integer> list = new ArrayList<>();
            for (int value : scoreArray) {
                sum += value;
                list.add(value);
            }
            for (int j = scoreArray.length; j > 0; j--) {
                if (sum % j == 0 && check(list, sum / j, sum / j)) {
                    System.out.println(sum / j);
                    return;
                }
            }
            System.out.println(sum);
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");
        }
    }

    @Test
    public void testBasketball(){
        //切割等和集合 动态规划 01背包解法
        Scanner scanner = new Scanner(System.in);
        Integer i = Integer.valueOf(scanner.nextLine());
        Integer[] integers = new Integer[i];
        for (int j = 0; j < i; j++) {
            integers[j] = scanner.nextInt();
        }
        boolean check = false;
        Integer sum = Arrays.stream(integers).reduce(0, Integer::sum);
        Arrays.sort(integers);
        for (int j = i; j > 1; j--) {
            boolean[] v=new boolean[i];
//            if (sum %j == 0 && dfs(integers, j, sum/j, 0, 0, v)) {
//                System.out.println(sum/j);
//                check = true;
//                break;
//            }
            if (canPartitionKSubsets(integers, j, sum)) {
                System.out.println(sum/j);
                check = true;
                break;
            }
        }
        if (!check) {
            System.out.println(sum);
        }

    }

    public static boolean dfs(Integer[] nums,int k, int sum){
        if (sum % k != 0){
            return false;
        }
        int target = sum / k;
        int length = nums.length;
        if (nums[length - 1] > target){
            return false;
        }
        boolean[] dp = new boolean[1 << length];
        int[] cacheSum = new int[1 << length];
        dp[0] = true;
        for (int i = 0; i < dp.length; i++) {
            if ( dp[i]){
                continue;
            }
            for (int j = 0; j < length; j++) {
                if (cacheSum[i] + nums[j] > target){
                    break;
                }
                if (((i >> j) & 1) == 0) {
                    int index = i | (1 << j);
                    if (!dp[index]){
                        cacheSum[index] = (cacheSum[i] + nums[j]) % target;
                        dp[index] = true;
                    }
                }
            }
        }
            return dp[dp.length - 1];
    }

    public static boolean canPartitionKSubsets(Integer[] nums, int k, int all) {
        if (all % k != 0) {
            return false;
        }
        int per = all / k;
        Arrays.sort(nums);
        int n = nums.length;
        if (nums[n - 1] > per) {
            return false;
        }
        boolean[] dp = new boolean[1 << n];
        int[] curSum = new int[1 << n];
        dp[0] = true;
        for (int i = 0; i < 1 << n; i++) {
            if (!dp[i]) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (curSum[i] + nums[j] > per) {
                    break;
                }
                if (((i >> j) & 1) == 0) {
                    int next = i | (1 << j);
                    if (!dp[next]) {
                        curSum[next] = (curSum[i] + nums[j]) % per;
                        dp[next] = true;
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }

    @Test
    public void checkTow(){
        for (int i = 0; i < 50; i++) {
            Integer []nums = new Integer[(int) (Math.random() * 50 + 1)];
            int k = (int) (Math.random() * nums.length + 1);
            Random random = new Random();

            for (int j = 0; j < nums.length; j++) {
                nums[j] = (int) (Math.random() * 10 + 1);
            }
            int sum = Arrays.stream(nums).reduce(0, Integer::sum);
            int target = sum / k;
            Arrays.sort(nums);
            System.out.println(Arrays.toString(nums));
            System.out.println(k + "-----" + target);
            boolean[] v = new boolean[nums.length];
            System.out.println( myCnBucket(nums, k) );
        }
    }

    public static boolean myCnBucket(Integer []nums, int k){
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0){
            return false;
        }
        int target = sum / k;
        Arrays.sort(nums);
        int index = 0;
        return buckets(nums, index, new int[k], target );

    }

    private static boolean buckets (Integer[] nums, int index, int[] buckets, int target) {
        if (index == nums.length){
            return true;
        }
        for (int i = 0; i < buckets.length; i++) {
            if (i > 0 && buckets[i] == buckets[i - 1]) {
                continue;
            }
            if (buckets[i] + nums[index] > target){
                continue;
            }
            buckets[i] = buckets[i] + nums[index];
            if (buckets(nums, index + 1, buckets, target)){
                return true;
            }
            buckets[i] = buckets[i] - nums[index];
        }
        return false;
    }
}
